#define _BSD_SOURCE
#include <unistd.h>
#include <stdio.h>
#include <stdint.h>
#include <string.h>
#include <stdlib.h>
#include <fcntl.h>
#include <errno.h>
#include <sys/stat.h>
#include <sys/types.h>
#include <sys/mman.h>

#include "config.h"
#include "zbd-cache.h"
#include "util/log.h"

typedef uint64_t blockaddr_t ;
typedef int zoneid_t ;
#define MMOD 100000003 // 哈希表大质数(建议比DIFFER_BLOCK大)
#define DIFFER_BLOCK 500000000 // 出现过的不同的块数
#define MAX_ACCRSS_LEN 1000000000 // trace 长度


// address / 64K = zone_id 

static int* Pages_Head; // MMAP -> Pages_Head[DIFFER_BLOCK]
static int* Pages_Nxt;  // MMAP -> Pages_Nxt[TRACE_LEN]

typedef struct linked_list{
    int * pre , * nxt; // [MAX_BLOCK+5]
    int first_element , last_element , cnt ;
    int (*get_next) ( void* , int ) ;
    int (*append) ( void* , int ) ;
    int (*get_first)( void* ) ;
    int (*erase)( void* , int ) ;
    int (*empty)( void* ) ;
} list_t ;
list_t Loginlist ;

static int list_t_get_next( void *t_ , int id ) {
    list_t *t = t_ ;
    return t->nxt[id] ;
}

static int list_t_get_first( void *t_ ){
    list_t *t = t_ ;
    return t->first_element ;
}

static int list_t_empty( void *t_ ) {
    list_t *t = t_ ;
    return t->cnt == 0 ;
}

static int list_t_append( void *t_ , int id ){
    list_t *t = t_ ;
    t->cnt ++ ;
    if( t->cnt == 1 ){ // insert the first element, no need to set pointer
        t->first_element = id ;
    } else {
        t->nxt[t->last_element] = id ;
        t->pre[id] = t->last_element ;
    }
    t->last_element = id ;
    return 0 ;
}

static int list_t_erase( void *t_ , int id ){
    list_t *t = t_ ;
    int preid = t->pre[id] , nxtid = t->nxt[id] ;
    if( preid != -1 ){
        t->nxt[preid] = nxtid ;
    }
    if( nxtid != -1 ){
        t->pre[nxtid] = preid ;
    }
    t->pre[id] = t->nxt[id] = -1 ;
    t->cnt -- ;
    if( t->last_element == id ){
        t->last_element = preid ;
    }
    if( t->first_element == id ){
        t->first_element = nxtid ;
    }
    return 0 ;
}


static blockaddr_t* TraceMAP;
typedef struct hash_translate{
    /*
    int head[MMOD+5] , <- malloc
        pre[DIFFER_BLOCK+5] , <- MMAP
        mapval[DIFFER_BLOCK+5] , <- MMAP
        tp ;
         
    blockaddr_t val[DIFFER_BLOCK+5] ;
    */
    int* head;
    int* pre;
    int* mapval;
    int tp ;
         
    blockaddr_t *val;
    int (*find) ( void* , blockaddr_t ) ;
    int (*insert) ( void* , blockaddr_t ) ;
} transtab_t ;
transtab_t transtab ;

static int transtab_t_find( void *t_ , blockaddr_t addr ) {
    transtab_t* t = t_ ;
    int id = addr % MMOD ;
    for( int i = t->head[id] ; i ; i = t->pre[i] ) {
        if( t->val[i] == addr ){
            return t->mapval[i] ;
        }
    }
    return -1 ;
}

static int transtab_t_insert( void *t_ , blockaddr_t addr ) {
    transtab_t *t = t_ ;
    int id = addr % MMOD ;
    ++t->tp  ;
    t->pre[t->tp] = t->head[id] ;
    t->head[id] = t->tp ;
    t->val[t->tp] = addr ;
    t->mapval[t->tp] = t->tp ;
    return 0 ;
}

// addrs: memory access list(0 base) , reqCnt: len of addrs[]
static int init( blockaddr_t *addrs , int reqCnt ){

    /* 初始化opt哈希表 */
    char hashmap_dir[128];
    sprintf(hashmap_dir, "%s-SUMRI-trace_%d", config_trace_hashmap_dir_prefix, STT.traceId);

    if(access(hashmap_dir, 0) == -1){
        mkdir(hashmap_dir, 0x0777);
    }


    transtab.head = (int*)calloc(MMOD + 5, sizeof(int));
    if(transtab.head == NULL){
        log_err_sac("[%s] error: %s\n", __func__, strerror(errno));
        exit(EXIT_FAILURE);
    }

    char hashfile_pre_path[128], hashfile_mapval_path[128], hashfile_val_path[128];
    sprintf(hashfile_pre_path, "%s/pre", hashmap_dir);
    sprintf(hashfile_mapval_path, "%s/mapval", hashmap_dir);
    sprintf(hashfile_val_path, "%s/val", hashmap_dir);

    int prefd, mapvalfd, valfd;
    prefd = open(hashfile_pre_path, O_RDWR | O_CREAT);
    mapvalfd = open(hashfile_mapval_path, O_RDWR | O_CREAT);
    valfd = open(hashfile_val_path, O_RDWR | O_CREAT);
    if ( prefd < 0 || mapvalfd < 0 || valfd < 0){
        log_err_sac("Open TracefileMap failed: %s\n", strerror(errno));
        exit(EXIT_FAILURE);
    }

    ftruncate(prefd, sizeof(int) * (DIFFER_BLOCK+5));
    ftruncate(mapvalfd, sizeof(int) * (DIFFER_BLOCK+5));
    ftruncate(valfd, sizeof(blockaddr_t) * (DIFFER_BLOCK+5));

    transtab.pre =      mmap(NULL, sizeof(int) * (DIFFER_BLOCK+5), PROT_READ | PROT_WRITE, MAP_SHARED, prefd, 0);
    transtab.mapval =   mmap(NULL, sizeof(int) * (DIFFER_BLOCK+5), PROT_READ | PROT_WRITE, MAP_SHARED, mapvalfd, 0);
    transtab.val =      mmap(NULL, sizeof(blockaddr_t) * (DIFFER_BLOCK+5), PROT_READ | PROT_WRITE, MAP_SHARED, valfd, 0);

    if (transtab.pre == (void *)-1 || transtab.mapval == (void *)-1 || transtab.val == (void *)-1)
    {
        log_err_sac("Create hashtabel mmap failed: %s\n", strerror(errno));
        exit(EXIT_FAILURE);
    }

    /* 初始化Pages_Head[] */
    char pageshead_path[128], pagesnxt_path[128];
    sprintf(pageshead_path, "%s/pageshead", hashmap_dir);
    sprintf(pagesnxt_path, "%s/pagesnxt", hashmap_dir);
    int pagesheadfd = open(pageshead_path, O_RDWR | O_CREAT); 
    int pagesnxtfd = open(pagesnxt_path, O_RDWR | O_CREAT); 
    ftruncate(pagesheadfd, sizeof(int) * DIFFER_BLOCK);
    ftruncate(pagesnxtfd, sizeof(int) * reqCnt);

    Pages_Head = mmap(NULL, sizeof(int) * DIFFER_BLOCK, PROT_READ | PROT_WRITE, MAP_SHARED, pagesheadfd, 0);
    Pages_Nxt =  mmap(NULL, sizeof(int) * reqCnt, PROT_READ | PROT_WRITE, MAP_SHARED, pagesnxtfd, 0); 
    if (Pages_Head == (void *)-1 || Pages_Nxt == (void *)-1)
    {
        log_err_sac("Create hashtabel mmap failed: %s\n", strerror(errno));
        exit(EXIT_FAILURE);
    }

    transtab.tp = 0 ;
    transtab.find = transtab_t_find ;
    transtab.insert = transtab_t_insert ;
    //memset( transtab.head , 0 , sizeof( transtab.head ) ) ; // calloc

    // head should init to be +inf , so that next[last] = inf 
    for(int i = 0; i < DIFFER_BLOCK; i++){
        Pages_Head[i] =  MAX_ACCRSS_LEN;
    }
    
    int tp = reqCnt ;
    for( int i = reqCnt - 1 ; i >= 0 ; i -- ){
        int mappedaddr = transtab.find( &transtab , addrs[i] ) ;
        if( mappedaddr < 0 ){
            transtab.insert( &transtab , addrs[i] ) ;
            mappedaddr = transtab.find( &transtab , addrs[i] ) ;
        }
        Pages_Nxt[--tp] = Pages_Head[mappedaddr] ;
        Pages_Head[mappedaddr] = tp ;
    }

    // 初始化Loginlist
    Loginlist.cnt = 0 ;
    Loginlist.first_element = Loginlist.last_element = -1 ;
    Loginlist.get_first = list_t_get_first ;
    Loginlist.get_next = list_t_get_next ;
    Loginlist.append = list_t_append ;
    Loginlist.erase = list_t_erase ;
    Loginlist.empty = list_t_empty ;

    int listsize = DIFFER_BLOCK > STT.n_cache_pages ? DIFFER_BLOCK + 5 : STT.n_cache_pages + 5;
    Loginlist.pre = (int *)malloc(sizeof(int) * listsize);
    Loginlist.nxt = (int *)malloc(sizeof(int) * listsize);
    if(Loginlist.pre == NULL || Loginlist.nxt == NULL){
        log_err_sac("LoginList malloc error.");
        exit(EXIT_FAILURE);
    }
    memset( Loginlist.pre , -1 , sizeof(int) * listsize ) ;
    memset( Loginlist.nxt , -1 , sizeof(int) * listsize ) ;

    return 0;
}

int sumRI_init()
{
    char tracemap[128];
    sprintf(tracemap, "%s_%d", config_trace_seq_mmap_file_prefix, STT.traceId);
    int maxMapReq = 2000000000;
    
    int tracemapfd = open(tracemap, O_RDONLY);
    if (tracemapfd < 0)
    {
        // open trace file
        
        if ((tracemapfd = open(tracemap, O_RDWR | O_CREAT)) < 0)
        {
            log_err_sac("Open TracefileMap failed: %s\n", strerror(errno));
            exit(EXIT_FAILURE);
        }
        ftruncate(tracemapfd, sizeof(uint64_t) * maxMapReq);

        TraceMAP = mmap(NULL, sizeof(uint64_t) * maxMapReq, PROT_READ | PROT_WRITE, MAP_SHARED, tracemapfd, 0);
        if (TraceMAP == (void *)-1)
        {
            log_err_sac("Create TraceMap failed: %s\n", strerror(errno));
            exit(EXIT_FAILURE);
        }

        FILE *trace = fopen(TRACE_FILES[STT.traceId], "rt");
        if (trace == NULL)
        {
            log_err_sac("Open trace file failed: %s\n", strerror(errno));
            exit(EXIT_FAILURE);
        };

        char action;
        uint64_t tg_blk;
        int mask;
        uint64_t *wrtReq = TraceMAP;
        uint64_t scanReqCnt = 0;
        while (!feof(trace)) // && scanReqCnt < STT.presetReq)
        {
            int ret;
#ifdef TRACE_SYSTOR17
            ret = fscanf(trace, "%c %d %lu\n", &action, &mask, &tg_blk);
#else
            ret = fscanf(trace, "%d %d %lu\n", &action, &mask, &tg_blk);
#endif

            if (ret < 0)
            {
                log_err_sac("error while reading trace file.");
                break;
            }

#ifdef TRACE_SYSTOR17
            tg_blk /= BLKSIZE;
#endif
            tg_blk += STT.start_Blkoff;

            if (action == ACT_WRITE && (STT.workload_mode & 0x02))
            {
                if ((tg_blk / N_ZONEBLK) > N_ZONES)
                {
                    log_info_sac("[warning] func:%s, target block overflow. \n", __func__);
                    continue;
                }

                *wrtReq = tg_blk;
                wrtReq++;
                scanReqCnt++;
            }
        }

        fclose(trace);
        msync(TraceMAP, sizeof(uint64_t) * maxMapReq, MS_SYNC);
        munmap(TraceMAP, sizeof(uint64_t) * maxMapReq);
        close(tracemapfd);
        // reopen
        if ((tracemapfd = open(tracemap, O_RDONLY)) < 0)
        {
            log_err_sac("Open TracefileMap failed: %s\n", strerror(errno));
            exit(EXIT_FAILURE);
        }
    }

    TraceMAP = mmap(NULL, sizeof(uint64_t) * maxMapReq, PROT_READ, MAP_SHARED, tracemapfd, 0);
    if (TraceMAP == (void *)-1)
    {
        log_err_sac("Create TraceMap failed: %s\n", strerror(errno));
        exit(EXIT_FAILURE);
    }

    init(TraceMAP, STT.presetReq + (4*STT.n_cache_pages));
    return 0;
}

static void movnext( blockaddr_t addr ){
    int mappedaddr = transtab.find( &transtab , addr ) ;
    Pages_Head[mappedaddr] = Pages_Nxt[ Pages_Head[mappedaddr] ] ;
}

static zoneid_t block_2_zone( blockaddr_t addr ) {
    return addr / N_ZONEBLK ;
}

// addr : login addr , op : useless
int sumRI_login( struct cache_page *page , int op ){
    int mappedaddr = transtab.find( &transtab , page->tg_blk ) ;
    Loginlist.append( &Loginlist , mappedaddr ) ;
    movnext( page->tg_blk ) ;
}

// call this function at every access , whether hit or not
// addr : accessed addr , op : useless
int sumRI_hit( struct cache_page *page , int op ){
    movnext( page->tg_blk ) ;
}

// addr : logout addr , op : useless
int sumRI_logout( struct cache_page *page , int op ){
    int mappedaddr = transtab.find( &transtab , page->tg_blk ) ;
    Loginlist.erase( &Loginlist , mappedaddr ) ;
}

// type : useless 
zoneid_t sumRI_writeback_privi( int type ){
    static uint64_t sumhead[N_ZONES+10] ;
    if( Loginlist.empty( &Loginlist ) ){
        return -1 ;
    }
    memset( sumhead , 0 , sizeof( sumhead ) ) ;
    for( int i = Loginlist.get_first( &Loginlist ) ; i != -1 ; i = Loginlist.get_next( &Loginlist , i ) ){
        int ri = Pages_Head[i] - STT.reqcnt_s - STT.resetReqSeq;
        if(ri > (int)STT.presetReq){
            ri = STT.presetReq; 
        }
        sumhead[ block_2_zone( transtab.val[i] ) ] += ri;
    }

    zoneid_t suggest = -1 ;
    struct zbd_zone * z, * z_suggest;
    for( int i = 0 ; i < N_ZONES ; i ++ ){
        z = zones_collection + i;
        if(z->cblks > 0){
            if(suggest == -1){
                suggest = i ;
                z_suggest = z;
                continue;
            }

            if(sumhead[suggest] < sumhead[i]) {
                suggest = i ;
                z_suggest = z;
            }
        }
    }

    if(suggest == -1){
        log_err_sac("error");
        exit(EXIT_FAILURE);
    }

    uint32_t rmw_scope = N_ZONEBLK;
    double wa = (double)rmw_scope / z_suggest->cblks_wtr;
    log_info_sac("[%s] WA: %.2f (%u/%u); \n", __func__, wa, rmw_scope, z_suggest->cblks_wtr);

    int dirty_pages = RMW(suggest, 0, N_ZONEBLK - 1);
    return suggest ;
}
